1. Field of the Invention
The present invention relates to routing of packets in a telecommunications network, and, more particularly, to allocating bandwidth capacity between nodes of a packet network using flow control for routing of packets.
2. Description of the Related Art
Service providers provision and maintain packet networks for clients having a variety of voice and data needs. For example, virtual private networks (VPNs) allow service providers to establish and tear down connections for a large number of users while only billing a single client. Each of these connections, which may be termed a session, may comprise a stream of packets, or packet flow, traversing links of the network. However, the client may require a certain amount of guaranteed bandwidth, minimum transport delay, or other metric for some or all of the packet flows transported through the network for a session. Routing methods may determine paths through links of the network and allocate portions of the corresponding bandwidth of the links to the sessions.
Network operators may commit to certain levels of service for sessions, such as guaranteed minimum available bandwidth or maximum packet-loss probability. Some networks, particularly high-speed networks, may support the networking protocol known as asynchronous transfer mode (ATM) in which data are transmitted as packets (termed xe2x80x9ccellsxe2x80x9d) through a logical path. Such high-speed networks typically carry multiple services having different traffic characteristics, including both constant bit rate traffic and variable bit rate traffic. One type of service provided in ATM networks is the available bit rate (ABR) service. Bandwidth commitments for the ABR service may include: 1) a minimum cell rate (MCR) available to a service (i.e., the least bandwidth that the network may allocate to a service), and 2) a peak cell rate (PCR) that the service may transmit cells (i.e., the maximum bandwidth that the network may allocate to a service). However, the network may require a mechanism for allocating bandwidth to the sessions sharing the total capacity of a link.
Packet networks of the prior art have employed a classic max-min (rate-allocation) policy as a mechanism for sharing bandwidth of the network for the ABR service. A max-min policy maximizes the minimum available bandwidth (i.e., cell rate) assigned to a session. FIG. 1 illustrates a network with sources S1 104 and S2 105 each establishing a point-to-point connection (session) with corresponding destinations D1 106 and D2 107. The bandwidth capacity for the connections passing through a link 103 between switches (SWs) 101 and 102 is shared. For the classic max-min policy, users that correspond to the source-destination pairs (S1 104 and D1 106) and (S2 105 and D2 107) each receives the same service level commitments from the service provider.
Each of the sources S1 104 and S2 105 initiating a session sends a request to the corresponding destination D1 106 or D2 107 to reserve bandwidth of the link 103 through which the connection passes. In ATM networks, this request is referred to as a resource management (RM) cell. The forward RM cell (from source to destination) contains the MCR and PCR values and an explicit cell rate (ER) set to the PCR value. A backward RM cell (from destination to source) contains the ER set to the assigned cell rate (i.e., allocated bandwidth). Typically, the bandwidth allocated to a connection by SWs 101 and 102 for each source-destination pair is the available bandwidth (remaining capacity) of link 103 divided by the number of connections. This classic max-min policy works well for a network when each session""s MCR is zero and each session""s PCR is greater than or equal to the link rate. However, for the general case of multiple users having different commitments for MCR/PCR, the classic max-min policy no longer determines rate allocation sufficiently since the classic max-min policy does not account for either the MCR or PCR of a user""s connection.
Other networks of the prior art providing ABR services may employ distributed algorithms to provide a max-min rate allocation for a sharing mechanism. In particular, the Consistent Marking method (outlined subsequently) for a distributed algorithm converges to the classical max-min policy through distributed and asynchronous iterations. The Consistent Marking method is described in, for example, A. Charny, D. Clark, and R. Jain, xe2x80x9cCongestion Control with Explicit Rate Indication,xe2x80x9d Proc. IEEE ICC""95 (1995) pp. 1954-1963.
According to the Consistent Marking method, each switch (e.g., SW 101 and 102 of FIG. 1) monitors the cell traffic traversing through the switch by keeping track of the state information of each session. Also, each output port of switches 101 and 102 maintains a variable, the advertised rate xcexc, to calculate available bandwidth (capacity) for each connection. An algorithm employing Consistent Marking method operates as follows.
When a forward RM cell arrives at SW 101, for example, the current cell rate (CCR) value of the session is stored in a virtual circuit (VC) table. If this CCR value is less than or equal to the current advertised rate xcexc, then the session is assumed to be in a bottlenecked state (i.e., the session cannot increase its cell rate because link capacity is unavailable), either at the link of the switch or at a link elsewhere within the network. Initially, the current advertised rate is set to the capacity of the link divided by the number of sessions traversing the link. A bit associated with this session is set (marked) within the VC table (the session having the corresponding VC table bit set is termed a xe2x80x9cmarked sessionxe2x80x9d). The advertised rate xcexc for the link is then calculated as given by equation (1):                               Advertised          ⁢                      xe2x80x83                    ⁢          Rate          ⁢                      xe2x80x83                    ⁢          μ                =                                            C              l                        -                          ∑                              xe2x80x83                            ⁢                              Rates                ⁢                                  xe2x80x83                                ⁢                of                ⁢                                  xe2x80x83                                ⁢                marked                ⁢                                  xe2x80x83                                ⁢                connections                                                                        n              l                        -                          ∑                              xe2x80x83                            ⁢                              Marked                ⁢                                  xe2x80x83                                ⁢                connections                                                                        (        1        )            
where Cl is the capacity of link l and nl is the number of connections of link l. The switch sets the ER field of the forward RM cell of the marked session to the calculated advertised rate xcexc. The advertised rate xcexc is continuously re-calculated as sessions are initiated, terminated, or updated.
For each re-calculation, the algorithm using the Consistent Marking method examines the entries of sessions in the VC table. For each marked session, if the recorded CCR of the marked session in the VC table is larger than the newly calculated advertised rate xcexc, the associated bit for the session is reset (the session is xe2x80x9cunmarkedxe2x80x9d) and the advertised rate xcexc is calculated again. Consequently, the ER field of the forward RM cell is set by the switches to the minimum of all advertised rates along the links traversed by the connection. The destination then returns a backward RM cell to the source with this ER value. Upon convergence of the Consistent Marking method, each session is allocated with a rate according to the max-min policy, and is marked along every link the session traverses. However, this method does not effectively account for the MCR and PCR of each session.
The present invention relates to allocating capacity of one or more links of a network by a router to a packet flow of at least one session, each session having a minimum rate and a peak rate. In accordance with the present invention, each session is initially assigned a rate based on the minimum rate of the session. A session is selected based on the initially assigned rate. An iterative procedure then increases the rate of the session if an available capacity of the link exists, and then determines whether the rate of the session that has been increased is equal to the corresponding peak rate of the session or the available capacity of the link. If the session that has been increased is equal to the corresponding peak rate of the session, then the rate of the session is set. If the session that has been increased is equal the available capacity of the link, then the rates of all sessions are set. The iterative procedure repeats for each of the sessions not having a set rate until all rates of the sessions are set, thereby maximizing the minimum rate assigned to each session of the link.